/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //
 //相交链表：两个链表只要相交，其尾结点一定相同，否则就不相交。
 //求交点：长的链表先走（长度差）步，再同时走，第一个相同的就是交点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    //遍历两个链表，得到节点数和尾结点
    int lenA = 1;
    while (tailA->next) {
        ++lenA;
        tailA = tailA->next;
    }

    int lenB = 1;
    while (tailB->next) {
        ++lenB;
        tailB = tailB->next;
    }
    //遍历到最后尾节点不相同则不相交
    if (tailA != tailB) {
        return NULL;
    }

    int gap = abs(lenA - lenB);

    //长的先走差距步，在同时往后走找交点
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;

    if (lenA < lenB) {
        shortList = headA;
        longList = headB;
    }

    while (gap--) {
        longList = longList->next;
    }

    while (longList != shortList) {
        longList = longList->next;
        shortList = shortList->next;
    }

    return longList;
}